1. The Field of the Invention
The present invention relates to communications technology, and more specifically, to mechanisms for pacing the transmission of network packets using a soft timer that is generated from at least partially uncorrelated network events.
2. Background and Relevant Art
Computing technology has transformed the way we work and play. Modem computer networking technologies and infrastructures allow for different applications and users to communicate data electronically even over vast distances relatively quickly using readily-available computing systems. Such computing systems may include, for example, desktop computers, laptop computers, Personal Digital Assistants (PDAs), digital telephones, or the like.
Currently, computing systems are so interconnected that one computing system is literally capable of communicating with any one of many millions of other computing systems spread throughout the globe. This is useful as we are now able to communicate more readily. In its most general form, communication between computing systems involves the formation of an electronic message. That electronic message is then broken down into smaller fragments. These fragments along with any appropriate header information are called “packets”.
The various packets of the electronic message are transmitted from a sending computing system to a receiving computing system. In order to properly route the packets, there are a number of intermediary computing systems that logically reside between the sending computing system and the receiving computing system. Typically, such intermediary computing systems receive and route packet transmissions coming from a large number of different computing systems.
In order to have the high scalability required to deal with the reception of packet transmissions from different computing systems, the intermediary computing system may have a queue, in which the packet is placed until the intermediary computing system can properly process the packet. The size of the queue is typically sufficient to handle some fluctuations in the packet receive rate. If there is a short-term period in which the packets are received faster than the intermediary computing system is capable of processing them, then the queue will fill more. On the other hand, if the packets are processed at a faster rate than there are received, the queue will empty more.
In suitable intermediary computing systems, the intermediary computing system is capable of processing the incoming requests at at least the average rate at which the packets are received. Accordingly, the queue tends towards being empty rather than being filled. This is because if the queue is filled, then packets may be dropped, thereby frustrating the purpose of the queue itself.
Even in suitable intermediary computing systems that are designed to process at a greater rate than the average packet receive rate, the queue may become overfilled in certain situations in which the packets arrive in a burst. This can happen in some feedback-oriented transmission protocols in which a sending computing system sends one or more packets in a burst, then waits for an acknowledgement from the receiving computing system before sending out more packets in a burst. The intensity of the phenomenon of packets arriving in bursts is often referred to herein as “burstiness”.
It is important to limit burstiness in the global Internet. To accomplish this in Transmission Control Protocol (TCP), the protocol most commonly used for data transfer over networks such as the Internet, the sending computing system typically sends two packets in a burst, and then waits for an acknowledgement message from the receiving computing system before sending out two more packets in a burst. However, this is an expensive method of limiting burstiness, since every acknowledgement packet sent by the receiver consumes resources on every intermediary computing system as well as the sending computing system. While it is important to limit burstiness on intermediary computing systems, it is also advantageous to reduce the number of packets emitted by the receiving computing system.
Having the receiver wait for more than two packets before emitting an acknowledgement packet has practical difficulties (it increases response time for short messages). An unconventional technology called Sender Moderated Acknowledgements allows the sender to indicate dynamically to the receiver which data packets it should acknowledge. Both of these methods increase the burstiness of packets on that particular connection.
One way to reduce the burstiness-of packet transmission is to pace the timing of the packets so that there is sufficient time between the sending of one packet and the sending of the next thereby stabilizing the packet transmission rate. Timing issues are typically controlled by a timer implemented in software within an operating system. Such timers typically operate on a scale of 10milliseconds or so. In fast networks that support one GigaBit Per Second (Gbps) transmission rates, this timing simply does not have sufficient granularity to pace packets. Even in the future, if faster timers were to become available, network transmission rates may go up as well. Accordingly, timer-based pacing of packet transmission is typically not considered a feasible option.
Accordingly, what would be advantageous are mechanisms for pacing the transmission of packets even though the operating system timer does not support fine enough clock increments to support such pacing.